package com.study.lu;

import java.util.Arrays;

public class 预测赢家 {
    /**
     * 给定一个数组，数组内都是正整数，现有两个玩家，轮流去取数组里面的数。只能从第一个或者最后一个取。不能重复取（即取完就没了）
     * 假设两个玩家都是最聪明的。都会追求他能得到的最高总分，请问谁会是最后的赢家
     * <p>
     * 如果数组的个数是偶数。那么玩家1必赢
     * eg  1,100,2,3
     * <br/> 玩家1  第一步  如果 取1 那么100肯定被玩家2拿走 所以第一步就是取 3  剩下 1,100,2
     * <br/> 玩家2  第一步  如果 取1 那么100肯定被玩家1拿走 所以第一步就是取 2  剩下 1,100
     * <br/> 玩家1  第二步  很明显会取100
     * <p>
     * 如果数组个数是奇数。那么就没有必赢了。
     * eg  1,100,2,3,5
     * <br/> 玩家1  第一步  如果 取1 那么100肯定被玩家2拿走 所以第一步就是取 5  剩下 1,100,2,3
     * <br/> 玩家2  第一步  如果 取1 那么100肯定被玩家1拿走 所以第一步就是取 3  剩下 1,100,2
     * <br/> 玩家1  第二步  不管怎么取，都输了。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1, 100, 2, 3};

        int[] nums2 = new int[]{1, 100, 2, 3, 5};

        findMax(nums2);

    }

    private static void findMax(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int left = 0, right = nums.length - 1;
        int player1Score = doFindMax(nums, left, right);

        System.out.println(player1Score >= sum - player1Score);


    }

    private static int doFindMax(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int leftScore = 0, rightScore = 0;
        if (right - left == 1) {
            leftScore = nums[left];
            rightScore = nums[right];
        }
        // 1, 100, 2, 3
        // left
        if (right - left > 1) {
            // 取左边得分数 = 左边这个值本身得分数 + 对手留给我的最小值（因为对手肯定是选最大值得）
            // 最小值 （对手取左边 还是取右边）
            // 如果对手选了左边，那么留给我选得就是 [left+2,right] 这个区间
            // 如果对手选了右边，那么留给我选得就是 [left+1,right-1] 这个区间
            leftScore = nums[left] + Math.min(doFindMax(nums, left + 2, right), doFindMax(nums, left + 1, right - 1));

            rightScore = nums[right] + Math.min(doFindMax(nums, left, right - 2), doFindMax(nums, left + 1, right - 1));
        }

        return Math.max(leftScore, rightScore);
    }
}
